#ifndef ASAN_AVLTREE_H
#define ASAN_AVLTREE_H

#include "asan_internal_defs.h"
#include "asan_internal.h"

namespace __sanitizer {

typedef int height_t;

class AsanChunk {
public:
  uptr beg_addr;
  uptr end_addr;
  height_t height;
  int mode;
  struct AsanChunk *left;
  struct AsanChunk *right;
  struct AsanChunk *father;
  
  inline bool IsRedZoneChunk() {return mode == kAsanHeapLeftRedzoneMagic || mode == kAsanGlobalRedzoneMagic;}
  inline bool IsPoisonedChunk() {return mode < 0 || mode >= (1 << ASAN_SHADOW_SCALE);}
  inline uptr ChunkSize() {return end_addr - beg_addr + 1;}
  inline void* Beg() const {return (void*)beg_addr;}
  inline void* End() const {return (void*)end_addr;}
};

int Balance(AsanChunk *node);
AsanChunk *NewAsanChunk(uptr beg_addr, uptr end_addr, int mode);
void UpdateHeight(AsanChunk *node);
AsanChunk *RightRotate(AsanChunk *node);
AsanChunk *LeftRotate(AsanChunk *node);
AsanChunk *InsertChunk(AsanChunk *node, AsanChunk *new_node);
AsanChunk *MinValueChunk(AsanChunk *node);
AsanChunk *MaxValueChunk(AsanChunk* node);
AsanChunk *DeleteChunk(AsanChunk *node, uptr beg_addr);

inline height_t ChunkHeight(const AsanChunk* chunk) {
  return chunk == nullptr ? 0 : chunk->height;
}

inline bool ChunkAtLeft(const AsanChunk* anchor, const AsanChunk* chunk) {
  return chunk->end_addr < anchor->beg_addr;
}

inline bool ChunkAtRight(const AsanChunk* anchor, const AsanChunk* chunk) {
  return chunk->beg_addr > anchor->end_addr;
}

inline bool ChunkHasOverlap(const AsanChunk* node, const AsanChunk* chunk) {
  if ((chunk->beg_addr > node->beg_addr && chunk->beg_addr < node->end_addr) \
      || (chunk->end_addr > node->beg_addr && chunk->end_addr < node->end_addr))
    return true;
  return false;
}

inline bool EqualChunk(AsanChunk* node, AsanChunk* chunk) {
  if (node == nullptr && chunk == nullptr) return true;
  else if (node == nullptr || chunk == nullptr) return false;
  return (node->beg_addr == chunk->beg_addr && node->end_addr == chunk->end_addr);
}

} // namespace __sanitizer

#endif // ASAN_AVLTREE_H